import java.util.Stack;

public class IsValidSerialization {

    public boolean isValidSerialization1(String preorder) {
        String[] split = preorder.split(",");
        Stack<String> stack = new Stack<>();
        if (split[0].equals("#")) return split.length == 1;
        stack.push(split[0]);
        stack.push(split[0]);
        for (int i = 1; i < split.length; i++) {
            String s = split[i];
            if (stack.size() >= 1) {
                stack.pop();
            } else return false;
            if (!s.equals("#")) {
                stack.push(s);
                stack.push(s);
            }
        }
        return stack.size() == 0;
    }

    public boolean isValidSerialization(String preorder) {
        String[] split = preorder.split(",");
        if (split[0].equals("#")) return split.length == 1;
        int i = 2;
        for (int j = 1; j < split.length; j++) {
            --i;
            if (i < 0) return false;
            if (!split[j].equals("#")) i += 2;
        }
        return i == 0;
    }
}
